package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC_102_BinaryTreeLevelOrderTraversal {
    public static void main(String[] args) {

    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode [val=" + val + ", left=" + left + ", right=" + right + "]";
        }
    }

    static class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> resultList = new ArrayList<>();
            if (root == null)
                return resultList;
            List<Integer> levelStorage = new LinkedList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            queue.offer(null);
            while (queue.size() > 1) {
                TreeNode top = queue.poll();
                if (top == null) {
                    resultList.add(levelStorage);
                    queue.offer(null);
                    levelStorage = new LinkedList<>();
                } else {
                    levelStorage.add(top.val);
                    if (top.left != null)
                        queue.offer(top.left);
                    if (top.right != null)
                        queue.offer(top.right);
                }
            }
            resultList.add(levelStorage);
            return resultList;
        }
    }

}
